package leetcode.Hot100;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;

/**
 * @author Cheng Jun
 * Description: 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。
 * 滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。
 * @version 1.0
 * @date 2021/12/28 21:39
 * <p>
 * 1 <= nums.length <= 105
 * -104 <= nums[i] <= 104
 * 1 <= k <= nums.length
 * 额外收获：对 PriorityQueue的 remove(Object o) 有了更加深入的认识。remove(Object o)的时间复杂度是O(n)，因为里面调用的indexOf(Object o),
 * indexOf(Object o) 的实现是遍历整个 数组，因为堆是无法保证有序的。
 * @see PriorityQueue#remove(java.lang.Object)
 * @see PriorityQueue#indexOf(java.lang.Object)
 */
public class maxSlidingWindow {


    public static void main(String[] args) {
        for (int num : maxSlidingWindow1(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)) {
            System.out.println(num);
        }
    }

    // 239. 滑动窗口最大值
    // 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
    // 输出：[3,3,5,5,6,7]
    // 解释：
    // 滑动窗口的位置                最大值
    // ---------------               -----
    // [1  3  -1] -3  5  3  6  7       3
    //  1 [3  -1  -3] 5  3  6  7       3
    //  1  3 [-1  -3  5] 3  6  7       5
    //  1  3  -1 [-3  5  3] 6  7       5
    //  1  3  -1  -3 [5  3  6] 7       6
    //  1  3  -1  -3  5 [3  6  7]      7
    // 思路：其实这里使用暴力解法的话，就是对每个滑动窗口的数组 取一次最大值。
    // 这里我们可以优化成 优先队列 PriorityQueue，我想到使用优先队列，是因为滑动数组会不断地变化，先进的数字先出。
    // 同时，我们又希望获得这些数字的有序状态。题目做多了，就有了题感。
    // 时间复杂度：遍历是O(n)，remove操作是O(n) 总的时间复杂度是 O(n^2) 提交LeetCode超时
    static public int[] maxSlidingWindow(int[] nums, int k) {
        int length = nums.length;
        // 结果
        int[] res = new int[length - k + 1];
        // 队列大小为k 的大根堆
        PriorityQueue<Integer> numQueue = new PriorityQueue<>(k, Comparator.reverseOrder());
        // 先灌满 numQueue
        for (int i = 0; i < k; i++) {
            numQueue.add(nums[i]);
        }
        for (int i = k; i < length; i++) {
            res[i - k] = numQueue.peek();
            numQueue.remove(nums[i - k]);
            numQueue.add(nums[i]);
        }
        // 最后要看一下 numQueue的最大值
        res[res.length - 1] = numQueue.peek();
        return res;
    }

    // https://leetcode-cn.com/problems/sliding-window-maximum/solution/shuang-xiang-dui-lie-jie-jue-hua-dong-chuang-kou-2/
    static public int[] maxSlidingWindow1(int[] nums, int k) {
        if (nums.length == 1) return nums;
        // 双向队列 保存当前窗口最大值的数组位置 保证队列中数组位置的数值按从大到小排序
        LinkedList<Integer> queue = new LinkedList();
        // 结果数组
        int[] result = new int[nums.length - k + 1];
        // 遍历nums数组
        for (int i = 0; i < nums.length; i++) {
            // 保证从大到小 如果前面数小则需要依次弹出，直至满足要求
            while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
                queue.pollLast();
            }
            // 添加当前值对应的数组下标
            queue.addLast(i);
            // 判断当前队列中队首的值是否有效
            if (queue.peek() <= i - k) {
                queue.poll();
            }
            // 当窗口长度为k时 保存当前窗口中最大值
            if (i + 1 >= k) {
                result[i + 1 - k] = nums[queue.peek()];
            }
        }
        return result;
    }
}
